package com.leetcode.easy;

import com.leetcode.entity.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Classname MinDepth
 * @Description TODO
 * @Date 2020/9/19 16:04
 * @Created by zfl
 */
public class MinDepth {

    /**
     * @param root
     * @return
     * 深度优先搜索算法
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：39 MB, 在所有 Java 提交中击败了38.33%的用户
     */
    public int minDepth1(TreeNode root) {
        if(root == null) {
            return 0;
        }

        if(root.left == null && root.right == null) {
            return 1;
        }

        int minDep = Integer.MAX_VALUE;
        if(root.left != null) {
            minDep = Math.min(minDepth1(root.left), minDep);
        }
        if(root.right != null) {
            minDep = Math.min(minDepth1(root.right), minDep);
        }

        return minDep + 1;
    }

    /**
     * @param root
     * @return
     * 广度优先搜索算法
     */
    public class QueueNode {
        TreeNode node;
        int depth;
        public QueueNode(TreeNode node, int depth) {
            this.depth = depth;
            this.node = node;
        }
    }
    public int minDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<>();
        queue.offer(new QueueNode(root,1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if(node.left == null && node.right == null) {
                return depth;
            }
            if(node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1) );
            }
            if(node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }
        return 0;
    }
}
